home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 037a / ccunzip.zip / UNZ.PAS < prev    next >
Pascal/Delphi Source File  |  1989-09-09  |  30KB  |  1,265 lines

  1.  
  2. (*
  3.  * Copyright 1987, 1989 Samuel H. Smith;  All rights reserved
  4.  *
  5.  * This is a component of the ProDoor System.
  6.  * Do not distribute modified versions without my permission.
  7.  * Do not remove or alter this notice or any other copyright notice.
  8.  * If you use this in your own program you must distribute source code.
  9.  * Do not use any of this in a commercial product.
  10.  *
  11.  *)
  12.  
  13. (*
  14.  * UnZip - A simple zipfile extract utility
  15.  *
  16.  *)
  17.  
  18. {$I+}    {I/O checking}
  19. {$N-}    {Numeric coprocessor}
  20. {$V-}    {Relaxes string typing}
  21. {$B-}    {Boolean complete evaluation}
  22. {$S-}    {Stack checking}
  23. {$R-}    {Range checking}
  24. {$D+}    {Global debug information}
  25. {$L+}    {Local debug information}
  26.  
  27. {$M 5000,0,0} {minstack,minheap,maxheap}
  28.  
  29. program UnZip;
  30.  
  31. Uses
  32.    Dos, Mdosio;
  33.  
  34. const
  35.    version = 'UnZ:  Zipfile Extract v2.0 (PAS) of 09-09-89;  (C) 1989 S.H.Smith';
  36.  
  37.  
  38.  
  39. (*
  40.  * Data declarations for the archive text-view functions.
  41.  *
  42.  *)
  43.  
  44. (* ----------------------------------------------------------- *)
  45. (*
  46.  * ZIPfile layout declarations
  47.  *
  48.  *)
  49.  
  50. type
  51.    signature_type = longint;
  52.  
  53. const
  54.    local_file_header_signature = $04034b50;
  55.  
  56. type
  57.    local_file_header = record
  58.       version_needed_to_extract:    word;
  59.       general_purpose_bit_flag:     word;
  60.       compression_method:           word;
  61.       last_mod_file_time:           word;
  62.       last_mod_file_date:           word;
  63.       crc32:                        longint;
  64.       compressed_size:              longint;
  65.       uncompressed_size:            longint;
  66.       filename_length:              word;
  67.       extra_field_length:           word;
  68.    end;
  69.  
  70. const
  71.    central_file_header_signature = $02014b50;
  72.  
  73. type
  74.    central_directory_file_header = record
  75.       version_made_by:                 word;
  76.       version_needed_to_extract:       word;
  77.       general_purpose_bit_flag:        word;
  78.       compression_method:              word;
  79.       last_mod_file_time:              word;
  80.       last_mod_file_date:              word;
  81.       crc32:                           longint;
  82.       compressed_size:                 longint;
  83.       uncompressed_size:               longint;
  84.       filename_length:                 word;
  85.       extra_field_length:              word;
  86.       file_comment_length:             word;
  87.       disk_number_start:               word;
  88.       internal_file_attributes:        word;
  89.       external_file_attributes:        longint;
  90.       relative_offset_local_header:    longint;
  91.    end;
  92.  
  93. const
  94.    end_central_dir_signature = $06054b50;
  95.  
  96. type
  97.    end_central_dir_record = record
  98.       number_this_disk:                         word;
  99.       number_disk_with_start_central_directory: word;
  100.       total_entries_central_dir_on_this_disk:   word;
  101.       total_entries_central_dir:                word;
  102.       size_central_directory:                   longint;
  103.       offset_start_central_directory:           longint;
  104.       zipfile_comment_length:                   word;
  105.    end;
  106.  
  107.  
  108.  
  109. (* ----------------------------------------------------------- *)
  110. (*
  111.  * input file variables
  112.  *
  113.  *)
  114.  
  115. const
  116.    uinbufsize = 512;    {input buffer size}
  117. var
  118.    zipeof:      boolean;
  119.    csize:       longint;
  120.    cusize:      longint;
  121.    cmethod:     integer;
  122.    cflags:      word;
  123.  
  124.    ctime:       word;
  125.    cdate:       word;
  126.    inbuf:       array[1..uinbufsize] of byte;
  127.    inpos:       integer;
  128.    incnt:       integer;
  129.    pc:          byte;
  130.    pcbits:      byte;
  131.    pcbitv:      byte;
  132.    zipfd:       dos_handle;
  133.    zipfn:       dos_filename;
  134.  
  135.  
  136.  
  137. (* ----------------------------------------------------------- *)
  138. (*
  139.  * output stream variables
  140.  *
  141.  *)
  142.  
  143. var
  144.    outbuf:      array[0..8192] of byte; {8192 or more for rle look-back}
  145.    outpos:      longint;                {absolute position in outfile}
  146.    outcnt:      integer;
  147.    outfd:       dos_handle;
  148.    filename:    string;
  149.    extra:       string;
  150.  
  151.  
  152.  
  153. (* ----------------------------------------------------------- *)
  154.  
  155. type
  156.    Sarray = array[0..255] of string[64];
  157.  
  158. var
  159.    factor:     integer;
  160.    followers:  Sarray;
  161.    ExState:    integer;
  162.    C:          integer;
  163.    V:          integer;
  164.    Len:        integer;
  165.  
  166. const
  167.    hsize =     8192;
  168.  
  169. type
  170.    hsize_array_integer = array[0..hsize] of integer;
  171.    hsize_array_byte    = array[0..hsize] of byte;
  172.  
  173. var
  174.    prefix_of:  hsize_array_integer;
  175.    suffix_of:  hsize_array_byte;
  176.    stack:      hsize_array_byte;
  177.    stackp:     integer;
  178.  
  179.  
  180.  
  181.  
  182. (*
  183.  * Zipfile input/output handlers
  184.  *
  185.  *)
  186.  
  187.  
  188. (* ------------------------------------------------------------- *)
  189. procedure skip_csize;
  190. begin
  191.    dos_lseek(zipfd,csize,seek_cur);
  192.    zipeof := true;
  193.    csize := 0;
  194.    incnt := 0;
  195. end;
  196.  
  197.  
  198. (* ------------------------------------------------------------- *)
  199. procedure ReadByte(var x: byte);
  200. begin
  201.    if incnt = 0 then
  202.    begin
  203.       if csize = 0 then
  204.       begin
  205.          zipeof := true;
  206.          exit;
  207.       end;
  208.  
  209.       inpos := sizeof(inbuf);
  210.       if inpos > csize then
  211.          inpos := csize;
  212.       incnt := dos_read(zipfd,inbuf,inpos);
  213.  
  214.       inpos := 1;
  215.       dec(csize,incnt);
  216.    end;
  217.  
  218.    x := inbuf[inpos];
  219.    inc(inpos);
  220.    dec(incnt);
  221. end;
  222.  
  223.  
  224. (*
  225.  * Copyright 1987, 1989 Samuel H. Smith;  All rights reserved
  226.  *
  227.  * This is a component of the ProDoor System.
  228.  * Do not distribute modified versions without my permission.
  229.  * Do not remove or alter this notice or any other copyright notice.
  230.  * If you use this in your own program you must distribute source code.
  231.  * Do not use any of this in a commercial product.
  232.  *
  233.  *)
  234.  
  235. (******************************************************
  236.  *
  237.  * Procedure:  itoh
  238.  *
  239.  * Purpose:    converts an integer into a string of hex digits
  240.  *
  241.  * Example:    s := itoh(i);
  242.  *
  243.  *)
  244.  
  245. function itoh(i: longint): string;   {integer to hex conversion}
  246. var
  247.    h:   string;
  248.    w:   word;
  249.  
  250.    procedure digit(ix: integer; ii: word);
  251.    begin
  252.       ii := ii and 15;
  253.       if ii > 9 then 
  254.          ii := ii + 7 + ord('a') - ord('A');
  255.       h[ix] := chr(ii + ord('0'));
  256.    end;
  257.  
  258. begin
  259.    w := i and $FFFF;
  260.    h[0] := chr(4);
  261.    digit(1,w shr 12);
  262.    digit(2,w shr 8);
  263.    digit(3,w shr 4);
  264.    digit(4,w);
  265.    itoh := h;   
  266. end;
  267.  
  268.  
  269. (* ------------------------------------------------------------- *)
  270. procedure ReadBits(bits: integer; var result: integer);
  271.    {read the specified number of bits}
  272. const
  273.    bit:     integer = 0;
  274.    bitv:    integer = 0;
  275.    x:       integer = 0;
  276. begin
  277.    x := 0;
  278.    bitv := 1;
  279.  
  280.    for bit := 0 to bits-1 do
  281.    begin
  282.  
  283.       if pcbits > 0 then
  284.       begin
  285.          dec(pcbits);
  286.          pcbitv := pcbitv shl 1;
  287.       end
  288.       else
  289.  
  290.       begin
  291.          ReadByte(pc);
  292.          pcbits := 7;
  293.          pcbitv := 1;
  294.       end;
  295.  
  296.       if (pc and pcbitv) <> 0 then
  297.          x := x or bitv;
  298.  
  299.       bitv := bitv shl 1;
  300.    end;
  301.  
  302. (* writeln(bits,'-',itoh(x)); *)
  303.    result := x;
  304. end;
  305.  
  306.  
  307. (* ---------------------------------------------------------- *)
  308. procedure get_string(ln: word; var s: string);
  309. var
  310.    n: word;
  311. begin
  312.    if ln > 255 then
  313.       ln := 255;
  314.    n := dos_read(zipfd,s[1],ln);
  315.    s[0] := chr(ln);
  316. end;
  317.  
  318.  
  319. (* ------------------------------------------------------------- *)
  320. procedure OutByte (c: integer);
  321.    (* output each character from archive to screen *)
  322. begin
  323.    outbuf[outcnt {outpos mod sizeof(outbuf)} ] := c;
  324.    inc(outpos);
  325.    inc(outcnt);
  326.  
  327.    if outcnt = sizeof(outbuf) then
  328.    begin
  329.       dos_write(outfd,outbuf,outcnt);
  330.       outcnt := 0;
  331.       write('.');
  332.    end;
  333. end;
  334.  
  335.  
  336. (*
  337.  * expand 'reduced' members of a zipfile
  338.  *
  339.  *)
  340.  
  341. (*
  342.  * The Reducing algorithm is actually a combination of two
  343.  * distinct algorithms.  The first algorithm compresses repeated
  344.  * byte sequences, and the second algorithm takes the compressed
  345.  * stream from the first algorithm and applies a probabilistic
  346.  * compression method.
  347.  *
  348.  *)
  349.  
  350. function reduce_L(x: byte): byte;
  351. begin
  352.    case factor of
  353.       1: reduce_L := x and $7f;
  354.       2: reduce_L := x and $3f;
  355.       3: reduce_L := x and $1f;
  356.       4: reduce_L := x and $0f;
  357.    end;
  358. end;
  359.  
  360. function reduce_F(x: byte): byte;
  361. begin
  362.    case factor of
  363.       1: if x = 127 then reduce_F := 2 else reduce_F := 3;
  364.       2: if x = 63  then reduce_F := 2 else reduce_F := 3;
  365.       3: if x = 31  then reduce_F := 2 else reduce_F := 3;
  366.       4: if x = 15  then reduce_F := 2 else reduce_F := 3;
  367.    end;
  368. end;
  369.  
  370. function reduce_D(x,y: byte): word;
  371. begin
  372.    case factor of
  373.       1: reduce_D := ((x shr 7) and $01) * 256 + Y + 1;
  374.       2: reduce_D := ((x shr 6) and $03) * 256 + Y + 1;
  375.       3: reduce_D := ((x shr 5) and $07) * 256 + Y + 1;
  376.       4: reduce_D := ((x shr 4) and $0f) * 256 + Y + 1;
  377.    end;
  378. end;
  379.  
  380. function reduce_B(x: byte): word;
  381.    {number of bits needed to encode the specified number}
  382. begin
  383.    case x-1 of
  384.       0..1:    reduce_B := 1;
  385.       2..3:    reduce_B := 2;
  386.       4..7:    reduce_B := 3;
  387.       8..15:   reduce_B := 4;
  388.      16..31:   reduce_B := 5;
  389.      32..63:   reduce_B := 6;
  390.      64..127:  reduce_B := 7;
  391.    else        reduce_B := 8;
  392.    end;
  393. end;
  394.  
  395. procedure Expand(c: byte);
  396. const
  397.    DLE = 144;
  398. var
  399.    op:   longint;
  400.    i:    integer;
  401.  
  402. begin
  403.  
  404.    case ExState of
  405.         0:  if C <> DLE then
  406.                 outbyte(C)
  407.             else
  408.                 ExState := 1;
  409.  
  410.         1:  if C <> 0 then
  411.             begin
  412.                 V := C;
  413.                 Len := reduce_L(V);
  414.                 ExState := reduce_F(Len);
  415.             end
  416.             else
  417.             begin
  418.                 outbyte(DLE);
  419.                 ExState := 0;
  420.             end;
  421.  
  422.         2:  begin
  423.                Len := Len + C;
  424.                ExState := 3;
  425.             end;
  426.  
  427.         3:  begin
  428.                op := outpos-reduce_D(V,C);
  429.                for i := 0 to Len+2 do
  430.                begin
  431.                   if op < 0 then
  432.                      outbyte(0)
  433.                   else
  434.                      outbyte(outbuf[op mod sizeof(outbuf)]);
  435.                   inc(op);
  436.                end;
  437.  
  438.                ExState := 0;
  439.             end;
  440.    end;
  441. end;
  442.  
  443.  
  444. procedure LoadFollowers;
  445. var
  446.    x: integer;
  447.    i: integer;
  448.    b: integer;
  449. begin
  450.    for x := 255 downto 0 do
  451.    begin
  452.       ReadBits(6,b);
  453.       followers[x][0] := chr(b);
  454.  
  455.       for i := 1 to length(followers[x]) do
  456.       begin
  457.          ReadBits(8,b);
  458.          followers[x][i] := chr(b);
  459.       end;
  460.    end;
  461. end;
  462.  
  463.  
  464. (* ----------------------------------------------------------- *)
  465. procedure unReduce;
  466.    {expand probablisticly reduced data}
  467.  
  468. var
  469.    lchar:   integer;
  470.    lout:    integer;
  471.    I:       integer;
  472.  
  473. begin
  474.    factor := cmethod - 1;
  475.    if (factor < 1) or (factor > 4) then
  476.    begin
  477.       skip_csize;
  478.       exit;
  479.    end;
  480.  
  481.    ExState := 0;
  482.    LoadFollowers;
  483.    lchar := 0;
  484.  
  485.    while (not zipeof) and (outpos < cusize) do
  486.    begin
  487.  
  488.       if followers[lchar] = '' then
  489.          ReadBits( 8,lout )
  490.       else
  491.  
  492.       begin
  493.          ReadBits(1,lout);
  494.          if lout <> 0 then
  495.             ReadBits( 8,lout )
  496.          else
  497.          begin
  498.             ReadBits( reduce_B(length(followers[lchar])), I );
  499.             lout := ord( followers[lchar][I+1] );
  500.          end;
  501.       end;
  502.  
  503.       if zipeof then
  504.          exit;
  505.  
  506.       Expand( lout );
  507.       lchar := lout;
  508.    end;
  509.  
  510. end;
  511.  
  512.  
  513.  
  514. (*
  515.  * expand 'shrunk' members of a zipfile
  516.  *
  517.  *)
  518.  
  519. (*
  520.  * UnShrinking
  521.  * -----------
  522.  *
  523.  * Shrinking is a Dynamic Ziv-Lempel-Welch compression algorithm
  524.  * with partial clearing.  The initial code size is 9 bits, and
  525.  * the maximum code size is 13 bits.  Shrinking differs from
  526.  * conventional Dynamic Ziv-lempel-Welch implementations in several
  527.  * respects:
  528.  *
  529.  * 1)  The code size is controlled by the compressor, and is not
  530.  *     automatically increased when codes larger than the current
  531.  *     code size are created (but not necessarily used).  When
  532.  *     the decompressor encounters the code sequence 256
  533.  *     (decimal) followed by 1, it should increase the code size
  534.  *     read from the input stream to the next bit size.  No
  535.  *     blocking of the codes is performed, so the next code at
  536.  *     the increased size should be read from the input stream
  537.  *     immediately after where the previous code at the smaller
  538.  *     bit size was read.  Again, the decompressor should not
  539.  *     increase the code size used until the sequence 256,1 is
  540.  *     encountered.
  541.  *
  542.  * 2)  When the table becomes full, total clearing is not
  543.  *     performed.  Rather, when the compresser emits the code
  544.  *     sequence 256,2 (decimal), the decompressor should clear
  545.  *     all leaf nodes from the Ziv-Lempel tree, and continue to
  546.  *     use the current code size.  The nodes that are cleared
  547.  *     from the Ziv-Lempel tree are then re-used, with the lowest
  548.  *     code value re-used first, and the highest code value
  549.  *     re-used last.  The compressor can emit the sequence 256,2
  550.  *     at any time.
  551.  *
  552.  *)
  553.  
  554. procedure unShrink;
  555.  
  556. const
  557.    max_bits =  13;
  558.    init_bits = 9;
  559.    first_ent = 257;
  560.    clear =     256;
  561.    
  562. var
  563.    cbits:      integer;
  564.    maxcode:    integer;
  565.    free_ent:   integer;
  566.    maxcodemax: integer;
  567.    offset:     integer;
  568.    sizex:      integer;
  569.    finchar:    integer;
  570.    code:       integer;
  571.    oldcode:    integer;
  572.    incode:     integer;
  573.  
  574.  
  575. (* ------------------------------------------------------------- *)
  576. procedure partial_clear;
  577. var
  578.    pr:   integer;
  579.    cd:   integer;
  580.  
  581. begin
  582.    {mark all nodes as potentially unused}
  583.    for cd := first_ent to free_ent-1 do
  584.       word(prefix_of[cd]) := prefix_of[cd] or $8000;
  585.  
  586.  
  587.    {unmark those that are used by other nodes}
  588.    for cd := first_ent to free_ent-1 do
  589.    begin
  590.       pr := prefix_of[cd] and $7fff;    {reference to another node?}
  591.       if pr >= first_ent then           {flag node as referenced}
  592.          prefix_of[pr] := prefix_of[pr] and $7fff;
  593.    end;
  594.  
  595.  
  596.    {clear the ones that are still marked}
  597.    for cd := first_ent to free_ent-1 do
  598.       if (prefix_of[cd] and $8000) <> 0 then
  599.          prefix_of[cd] := -1;
  600.  
  601.  
  602.    {find first cleared node as next free_ent}
  603.    free_ent := first_ent;
  604.    while (free_ent < maxcodemax) and (prefix_of[free_ent] <> -1) do
  605.       inc(free_ent);
  606. end;
  607.  
  608.  
  609. (* ------------------------------------------------------------- *)
  610. begin
  611.    (* decompress the file *)
  612.    maxcodemax := 1 shl max_bits;
  613.    cbits := init_bits;
  614.    maxcode := (1 shl cbits)- 1;
  615.    free_ent := first_ent;
  616.    offset := 0;
  617.    sizex := 0;
  618.  
  619.    fillchar(prefix_of,sizeof(prefix_of),$FF);
  620.    for code := 255 downto 0 do
  621.    begin
  622.       prefix_of[code] := 0;
  623.       suffix_of[code] := code;
  624.    end;
  625.  
  626.    ReadBits(cbits,oldcode);
  627.    if zipeof then
  628.       exit;
  629.    finchar := oldcode;
  630.  
  631.    OutByte(finchar);
  632.  
  633.    stackp := 0;
  634.  
  635.    while (not zipeof) do
  636.    begin
  637.       ReadBits(cbits,code);
  638.       if zipeof then
  639.          exit;
  640.  
  641.       while (code = clear) do
  642.       begin
  643.          ReadBits(cbits,code);
  644.  
  645.          case code of
  646.             1: begin
  647.                   inc(cbits);
  648.                   if cbits = max_bits then
  649.                      maxcode := maxcodemax
  650.                   else
  651.                      maxcode := (1 shl cbits) - 1;
  652.                end;
  653.  
  654.             2: partial_clear;
  655.          end;
  656.  
  657.          ReadBits(cbits,code);
  658.          if zipeof then
  659.             exit;
  660.       end;
  661.  
  662.  
  663.       {special case for KwKwK string}
  664.       incode := code;
  665.       if prefix_of[code] = -1 then
  666.       begin
  667.          stack[stackp] := finchar;
  668.          inc(stackp);
  669.          code := oldcode;
  670.       end;
  671.  
  672.  
  673.       {generate output characters in reverse order}
  674.       while (code >= first_ent) do
  675.       begin
  676.          stack[stackp] := suffix_of[code];
  677.          inc(stackp);
  678.          code := prefix_of[code];
  679.       end;
  680.  
  681.       finchar := suffix_of[code];
  682.       stack[stackp] := finchar;
  683.       inc(stackp);
  684.  
  685.  
  686.       {and put them out in forward order}
  687.       while (stackp > 0) do
  688.       begin
  689.          dec(stackp);
  690.          OutByte(stack[stackp]);
  691.       end;
  692.  
  693.  
  694.       {generate new entry}
  695.       code := free_ent;
  696.       if code < maxcodemax then
  697.       begin
  698.          prefix_of[code] := oldcode;
  699.          suffix_of[code] := finchar;
  700.          while (free_ent < maxcodemax) and (prefix_of[free_ent] <> -1) do
  701.             inc(free_ent);
  702.       end;
  703.  
  704.  
  705.       {remember previous code}
  706.       oldcode := incode;
  707.    end;
  708.  
  709. end;
  710.  
  711.  
  712.  
  713. (* ------------------------------------------------------------- *)
  714. (*
  715.  * Imploding
  716.  * ---------
  717.  *
  718.  * The Imploding algorithm is actually a combination of two distinct
  719.  * algorithms.  The first algorithm compresses repeated byte sequences
  720.  * using a sliding dictionary.  The second algorithm is used to compress
  721.  * the encoding of the sliding dictionary ouput, using multiple
  722.  * Shannon-Fano trees.
  723.  *
  724.  *)
  725.  
  726. const
  727.    maxSF = 256;
  728.  
  729. type
  730.    sf_entry = record
  731.                  Code:       word;
  732.                  Value:      byte;
  733.                  BitLength:  byte;
  734.               end;
  735.  
  736.    sf_tree = record  {a shannon-fano tree}
  737.       entry:         array[0..maxSF] of sf_entry;
  738.       entries:       integer;
  739.       MaxLength:     integer;
  740.    end;
  741.  
  742.    sf_treep = ^sf_tree;
  743.  
  744. var
  745.    lit_tree:               sf_tree;
  746.    length_tree:            sf_tree;
  747.    distance_tree:          sf_tree;
  748.    lit_tree_present:       boolean;
  749.    eightK_dictionary:      boolean;
  750.    minimum_match_length:   integer;
  751.    dict_bits:              integer;
  752.  
  753.  
  754. procedure SortLengths(var tree: sf_tree);
  755.    {Sort the Bit Lengths in ascending order, while retaining the order
  756.     of the original lengths stored in the file}
  757. var
  758.    x:       integer;
  759.    gap:     integer;
  760.    t:       sf_entry;
  761.    noswaps: boolean;
  762.    a,b:     integer;
  763.  
  764. begin
  765.    gap := tree.entries div 2;
  766.  
  767.    repeat
  768.       repeat
  769.          noswaps := true;
  770.          for x := 0 to (tree.entries-1)-gap do
  771.          begin
  772.             a := tree.entry[x].BitLength;
  773.             b := tree.entry[x+gap].BitLength;
  774.             if (a > b) or
  775.                ((a = b) and (tree.entry[x].Value > tree.entry[x+gap].Value)) then
  776.             begin
  777.                t := tree.entry[x];
  778.                tree.entry[x] := tree.entry[x+gap];
  779.                tree.entry[x+gap] := t;
  780.                noswaps := false;
  781.             end;
  782.          end;
  783.       until noswaps;
  784.  
  785.       gap := gap div 2;
  786.    until gap < 1;
  787. end;
  788.  
  789.  
  790. (* ----------------------------------------------------------- *)
  791. procedure ReadLengths(var tree: sf_tree);
  792. var
  793.    treeBytes:  integer;
  794.    i:          integer;
  795.    num,len:    integer;
  796.  
  797. begin
  798.    {get number of bytes in compressed tree}
  799.    ReadBits(8,treeBytes);
  800.    inc(treeBytes);
  801.    i := 0;
  802.  
  803.    begin
  804.       tree.MaxLength := 0;
  805.  
  806.       {High 4 bits: Number of values at this bit length + 1. (1 - 16)
  807.        Low  4 bits: Bit Length needed to represent value + 1. (1 - 16)}
  808.       while treeBytes > 0 do
  809.       begin
  810.          ReadBits(4,len);  inc(len);
  811.          ReadBits(4,num);  inc(num);
  812.  
  813.          while num > 0 do
  814.          begin
  815.             if len > tree.MaxLength then
  816.                tree.MaxLength := len;
  817.             tree.entry[i].BitLength := len;
  818.             tree.entry[i].Value := i;
  819.             inc(i);
  820.             dec(num);
  821.          end;
  822.  
  823.          dec(treeBytes);
  824.       end;
  825.    end;
  826. end;
  827.  
  828.  
  829. (* ----------------------------------------------------------- *)
  830. procedure GenerateTrees(var tree: sf_tree);
  831.    {Generate the Shannon-Fano trees}
  832. var
  833.    Code:          word;
  834.    CodeIncrement: integer;
  835.    LastBitLength: integer;
  836.    i:             integer;
  837.  
  838. begin
  839.    Code := 0;
  840.    CodeIncrement := 0;
  841.    LastBitLength := 0;
  842.  
  843.    i := tree.entries - 1;   {either 255 or 63}
  844.    while i >= 0 do
  845.    begin
  846.       inc(Code,CodeIncrement);
  847.       if tree.entry[i].BitLength <> LastBitLength then
  848.       begin
  849.          LastBitLength := tree.entry[i].BitLength;
  850.          CodeIncrement := 1 shl (16 - LastBitLength);
  851.       end;
  852.  
  853.       tree.entry[i].Code := Code;
  854.       dec(i);
  855.    end;
  856. end;
  857.  
  858.  
  859. (* ----------------------------------------------------------- *)
  860. procedure ReverseBits(var tree: sf_tree);
  861.    {Reverse the order of all the bits in the above ShannonCode[]
  862.     vector, so that the most significant bit becomes the least
  863.     significant bit. For example, the value 0x1234 (hex) would become
  864.     0x2C48 (hex).}
  865. var
  866.    i:    integer;
  867.    mask: word;
  868.    revb: word;
  869.    v:    word;
  870.    o:    word;
  871.    b:    integer;
  872.  
  873. begin
  874.    for i := 0 to tree.entries-1 do
  875.    begin
  876.       {get original code}
  877.       o := tree.entry[i].Code;
  878.  
  879.       {reverse each bit}
  880.       mask := $0001;
  881.       revb := $8000;
  882.       v := 0;
  883.       for b := 0 to 15 do
  884.       begin
  885.          {if bit set in mask, then substitute reversed bit}
  886.          if (o and mask) <> 0 then
  887.             v := v or revb;
  888.  
  889.          {advance to next bit}
  890.          revb := revb shr 1;
  891.          mask := mask shl 1;
  892.       end;
  893.  
  894.       {store reversed bits}
  895.       tree.entry[i].Code := v;
  896.    end;
  897. end;
  898.  
  899.  
  900. (* ----------------------------------------------------------- *)
  901. procedure LoadTree(var tree: sf_tree;
  902.                    treesize: integer);
  903.    {allocate and load a shannon-fano tree from the compressed file}
  904. begin
  905.    tree.entries := treesize;
  906.    ReadLengths(tree);
  907.    SortLengths(tree);
  908.    GenerateTrees(tree);
  909.    ReverseBits(tree);
  910. end;
  911.  
  912.  
  913. (* ----------------------------------------------------------- *)
  914. procedure LoadTrees;
  915. begin
  916.    eightK_dictionary := (cflags and $02) <> 0; {bit 1}
  917.    lit_tree_present := (cflags and $04) <> 0; {bit 2}
  918.  
  919.    if eightK_dictionary then
  920.       dict_bits := 7
  921.    else
  922.       dict_bits := 6;
  923.  
  924.    if lit_tree_present then
  925.    begin
  926.       minimum_match_length := 3;
  927.       LoadTree(lit_tree,256);
  928.    end
  929.    else
  930.       minimum_match_length := 2;
  931.  
  932.    LoadTree(length_tree,64);
  933.    LoadTree(distance_tree,64);
  934. end;
  935.  
  936.  
  937. (* ----------------------------------------------------------- *)
  938. procedure ReadTree(var tree: sf_tree;
  939.                    var dest: integer);
  940.    {read next byte using a shannon-fano tree}
  941. var
  942.    bits: integer;
  943.    cv:   word;
  944.    b:    integer;
  945.    cur:  integer;
  946.  
  947. begin
  948.    bits := 0;
  949.    cv := 0;
  950.    cur := 0;
  951.    dest := -1; {in case of error}
  952.  
  953.    while true do
  954.    begin
  955.       ReadBits(1,b);
  956.       cv := cv or (b shl bits);
  957.       inc(bits);
  958.  
  959.       (* this is a very poor way of decoding shannon-fano.  two quicker
  960.       methods come to mind:
  961.          a) arrange the tree as a huffman-style binary tree with
  962.             a "leaf" indicator at each node,
  963.       and
  964.          b) take advantage of the fact that s-f codes are at most 8
  965.             bits long and alias unused codes for all bits following
  966.             the "leaf" bit.
  967.       *)
  968.  
  969.       while tree.entry[cur].BitLength < bits do
  970.       begin
  971.          inc(cur);
  972.          if cur >= tree.entries then
  973.             exit;
  974.       end;
  975.  
  976.       while tree.entry[cur].BitLength = bits do
  977.       begin
  978.          if tree.entry[cur].Code = cv then
  979.          begin
  980.             dest := tree.entry[cur].Value;
  981.             exit;
  982.          end;
  983.  
  984.          inc(cur);
  985.          if cur >= tree.entries then
  986.             exit;
  987.       end;
  988.    end;
  989. end;
  990.  
  991.  
  992. (* ----------------------------------------------------------- *)
  993. procedure unImplode;
  994.    {expand imploded data}
  995.  
  996. var
  997.    lout:       integer;
  998.    op:         longint;
  999.    Length:     integer;
  1000.    Distance:   integer;
  1001.    i:          integer;
  1002.  
  1003. begin
  1004.    LoadTrees;
  1005.  
  1006.    while (not zipeof) and (outpos < cusize) do
  1007.    begin
  1008.       ReadBits(1,lout);
  1009.  
  1010.       if lout <> 0 then    {encoded data is literal data}
  1011.       begin
  1012.          if lit_tree_present then
  1013.             ReadTree(lit_tree,lout)   {use Literal Shannon-Fano tree}
  1014.          else
  1015.             ReadBits(8,lout);
  1016.  
  1017.          OutByte(lout);
  1018.       end
  1019.       else
  1020.  
  1021.       begin          {encoded data is sliding dictionary match}
  1022.          readBits(dict_bits,lout);
  1023.          Distance := lout;
  1024.  
  1025.          ReadTree(distance_tree,lout);
  1026.          Distance := Distance or (lout shl dict_bits);
  1027.          {using the Distance Shannon-Fano tree, read and decode the
  1028.             upper 6 bits of the Distance value}
  1029.  
  1030.          ReadTree(length_tree,Length);
  1031.          {using the Length Shannon-Fano tree, read and decode the Length value}
  1032.  
  1033.          inc(Length,Minimum_Match_Length);
  1034.          if Length = (63 + Minimum_Match_Length) then
  1035.          begin
  1036.             ReadBits(8,lout);
  1037.             inc(Length,lout);
  1038.          end;
  1039.  
  1040.          {move backwards Distance+1 bytes in the output stream, and copy
  1041.           Length characters from this position to the output stream.
  1042.           (if this position is before the start of the output stream,
  1043.           then assume that all the data before the start of the output
  1044.           stream is filled with zeros)}
  1045.  
  1046.          op := outpos - Distance - 1;
  1047.          for i := 1 to Length do
  1048.          begin
  1049.             if op < 0 then
  1050.                OutByte(0)
  1051.             else
  1052.                OutByte(outbuf[op mod sizeof(outbuf)]);
  1053.             inc(op);
  1054.          end;
  1055.       end;
  1056.    end;
  1057. end;
  1058.  
  1059.  
  1060.  
  1061. (*
  1062.  * This procedure displays the text contents of a specified archive
  1063.  * file.  The filename must be fully specified and verified.
  1064.  *
  1065.  *)
  1066.  
  1067.  
  1068. (* ---------------------------------------------------------- *)
  1069. procedure extract_member;
  1070. var
  1071.    b: byte;
  1072.  
  1073. begin
  1074.    pcbits := 0;
  1075.    incnt := 0;
  1076.    outpos := 0;
  1077.    outcnt := 0;
  1078.    zipeof := false;
  1079.  
  1080.    outfd := dos_create(filename);
  1081.    if outfd = dos_error then
  1082.    begin
  1083.       writeln('Can''t create output: ', filename);
  1084.       halt;
  1085.    end;
  1086.  
  1087.    case cmethod of
  1088.       0:    {stored}
  1089.             begin
  1090.                write(' Extract: ',filename,' ...');
  1091.                while (not zipeof) do
  1092.                begin
  1093.                   ReadByte(b);
  1094.                   OutByte(b);
  1095.                end;
  1096.             end;
  1097.  
  1098.       1:    begin
  1099.                write('UnShrink: ',filename,' ...');
  1100.                UnShrink;
  1101.             end;
  1102.  
  1103.       2..5: begin
  1104.                write('  Expand: ',filename,' ...');
  1105.                UnReduce;
  1106.             end;
  1107.  
  1108.       6:    begin
  1109.                write(' Explode: ',filename,' ...');
  1110.                unImplode;
  1111.             end;
  1112.  
  1113.       else  write('Unknown compression method.');
  1114.    end;
  1115.  
  1116.    if outcnt > 0 then
  1117.       dos_write(outfd,outbuf,outcnt);
  1118.  
  1119.    dos_file_times(outfd,time_set,ctime,cdate);
  1120.    dos_close(outfd);
  1121.  
  1122.    writeln('  done.');
  1123. end;
  1124.  
  1125.  
  1126. (* ---------------------------------------------------------- *)
  1127. procedure process_local_file_header;
  1128. var
  1129.    n:             word;
  1130.    rec:           local_file_header;
  1131.  
  1132. begin
  1133.    n := dos_read(zipfd,rec,sizeof(rec));
  1134.    get_string(rec.filename_length,filename);
  1135.    get_string(rec.extra_field_length,extra);
  1136.    csize := rec.compressed_size;
  1137.    cusize := rec.uncompressed_size;
  1138.    cmethod := rec.compression_method;
  1139.    cflags := rec.general_purpose_bit_flag;
  1140.    ctime := rec.last_mod_file_time;
  1141.    cdate := rec.last_mod_file_date;
  1142.    extract_member;
  1143. end;
  1144.  
  1145.  
  1146. (* ---------------------------------------------------------- *)
  1147. procedure process_central_file_header;
  1148. var
  1149.    n:             word;
  1150.    rec:           central_directory_file_header;
  1151.    filename:      string;
  1152.    extra:         string;
  1153.    comment:       string;
  1154.  
  1155. begin
  1156.    n := dos_read(zipfd,rec,sizeof(rec));
  1157.    get_string(rec.filename_length,filename);
  1158.    get_string(rec.extra_field_length,extra);
  1159.    get_string(rec.file_comment_length,comment);
  1160. end;
  1161.  
  1162.  
  1163. (* ---------------------------------------------------------- *)
  1164. procedure process_end_central_dir;
  1165. var
  1166.    n:             word;
  1167.    rec:           end_central_dir_record;
  1168.    comment:       string;
  1169.  
  1170. begin
  1171.    n := dos_read(zipfd,rec,sizeof(rec));
  1172.    get_string(rec.zipfile_comment_length,comment);
  1173. end;
  1174.  
  1175.  
  1176. (* ---------------------------------------------------------- *)
  1177. procedure process_headers;
  1178. var
  1179.    sig:  longint;
  1180.  
  1181. begin
  1182.    dos_lseek(zipfd,0,seek_start);
  1183.  
  1184.    while true do
  1185.    begin
  1186.       if dos_read(zipfd,sig,sizeof(sig)) <> sizeof(sig) then
  1187.          exit
  1188.       else
  1189.  
  1190.       if sig = local_file_header_signature then
  1191.          process_local_file_header
  1192.       else
  1193.  
  1194.       if sig = central_file_header_signature then
  1195.          process_central_file_header
  1196.       else
  1197.  
  1198.       if sig = end_central_dir_signature then
  1199.       begin
  1200.          process_end_central_dir;
  1201.          exit;
  1202.       end
  1203.  
  1204.       else
  1205.       begin
  1206.          writeln('Invalid Zipfile Header');
  1207.          exit;
  1208.       end;
  1209.    end;
  1210.  
  1211. end;
  1212.  
  1213.  
  1214. (* ---------------------------------------------------------- *)
  1215. procedure extract_zipfile;
  1216. begin
  1217.    zipfd := dos_open(zipfn,open_read);
  1218.    if zipfd = dos_error then
  1219.       exit;
  1220.  
  1221.    process_headers;
  1222.  
  1223.    dos_close(zipfd);
  1224. end;
  1225.  
  1226.  
  1227. (*
  1228.  * main program
  1229.  *
  1230.  *)
  1231.  
  1232. begin
  1233.    if paramcount <> 1 then
  1234.    begin
  1235.       writeln;
  1236.       writeln(version);
  1237.       writeln('Courtesy of:  S.H.Smith  and  The Tool Shop BBS,  (602) 279-2673.');
  1238.       writeln;
  1239.       writeln('You may copy and distribute this program freely, provided that:');
  1240.       writeln('    1)   No fee is charged for such copying and distribution, and');
  1241.       writeln('    2)   It is distributed ONLY in its original, unmodified state.');
  1242.       writeln('If you wish to distribute a modified version of this program, you MUST');
  1243.       writeln('include the source code.');
  1244.       writeln;
  1245.       writeln('If you modify this program, I would appreciate a copy of the  new source');
  1246.       writeln('code.   I am holding the copyright on the source code, so please don''t');
  1247.       writeln('delete my name from the program files or from the documentation.');
  1248.       writeln('IN NO EVENT WILL I BE LIABLE TO YOU FOR ANY DAMAGES, INCLUDING ANY LOST');
  1249.       writeln('PROFITS, LOST SAVINGS OR OTHER INCIDENTAL OR CONSEQUENTIAL DAMAGES');
  1250.       writeln('ARISING OUT OF YOUR USE OR INABILITY TO USE THE PROGRAM, OR FOR ANY');
  1251.       writeln('CLAIM BY ANY OTHER PARTY.');
  1252.       writeln;
  1253.       writeln('Usage:  UnZip FILE[.zip]');
  1254.       halt;
  1255.    end;
  1256.  
  1257.    zipfn := paramstr(1);
  1258.    if pos('.',zipfn) = 0 then
  1259.       zipfn := zipfn + '.ZIP';
  1260.  
  1261.    extract_zipfile;
  1262. end.
  1263.  
  1264.  
  1265.